package 力扣.链表.交换;

import java.util.List;

public class k个一组反转链表25 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        int k = 2;
//        reverseKGroup2(head, k);
        reverse(head);
    }
    //反转一条链表工具类
    public  static ListNode reverse(ListNode head){
        ListNode dummy = null;
        while (head != null){
            ListNode tmp = head.next;
            head.next= dummy.next;
            dummy.next = head;
            head = tmp;
        }
        return  dummy.next;
    }
    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode();
//        ListNode newHead = head;
        ListNode teans = dummy;//当前结果
        while (head != null){
            int i = 0;
            ListNode tail = teans;//teans暂时反转 前的节点
            ListNode p = head;//需要反转的链表的头节点，反转之后就变成了尾节点
            while (head != null){
                if (i >= k){
                    break;
                }
                ListNode te = head;
                head = head.next;//提前变
                te.next = tail.next;
                tail.next = te;
//                p = p.next;
                i++;
            }
            if (i < k){
                //在同一条链表上实现反转 十分重要♥♥♥
                ListNode tehead = teans.next;
                tehead = tehead.next;
                teans.next.next = null;//不处理的话会形成环（死循环）
                while (tehead != null){
                    ListNode te = tehead;
                    tehead = tehead.next;//提前跑
                    te.next = teans.next;
                    teans.next = te;
                }

            }else {
                teans = p;
            }
        }
        return dummy.next;
    }
    public static ListNode reverseKGroup2(ListNode head, int k) {
           int nums = 0;
           ListNode tmp = head;
           while (tmp !=null && nums < k){
               tmp = tmp.next;
               nums++;
           }
           if (nums == k){
               //局部反转
               ListNode t1 = head;
               ListNode t2 = null;
               ListNode pre = null;
              while (nums-- > 0 && t1 != null){
                  t2 = t1.next;
                  t1.next = pre;
                  pre = t1;
                  t1 = t2;
              }
              if (t2 != null){
                  head.next = reverseKGroup2(t2,k);
              }
              return pre;
           }else {
              return head;
           }
    }

    public ListNode reverseKGroup3(ListNode head, int k) {
          return reverse(head, k);
    }
    private ListNode reverse(ListNode root,int k){
        if (root == null){
            return null;
        }
        ListNode head = root;
        int i = 0;
        while (root != null && i < k){
            root = root.next;
            i++;
        }

        if (i == k){//反转链表(反指法)
            ListNode pre = null;
            ListNode te1 = head;
            while (te1 != null && i-- > 0){
                ListNode te2 = te1.next;
                te1.next = pre;
                pre = te1;
                te1 = te2;
            }
            head.next = reverse(te1, k);
            return pre;
        }else {
            return head;
        }
    }

}
